Disc drives are data storage devices that store digital data in magnetic form on a rotating storage medium called a disc. Modem disc drives comprise one or more rigid discs that are coated with a magnetizable medium and mounted on the hub of a spindle motor for rotation at a constant high speed. Each surface of a disc is divided into several thousand tracks that are tightly-packed concentric circles similar in layout to the annual growth rings of a tree. The tracks are typically numbered starting from zero at the track located outermost the disc and increasing for tracks located closer to the center of the disc. Each track is further broken down into sectors. A sector is normally the smallest individually addressable unit of information stored in a disc drive and typically holds 512 bytes of information plus a few additional bytes for internal drive control and error detection and correction. This organization of data allows for easy access to any part of the discs.
Generally, each of the multiple discs in a disc drive has associated with it two heads (one adjacent the top surface of the disc, and another adjacent the bottom) for reading and writing data to a sector. A typical disc drive has two or three discs. This usually means four or six heads in a disc drive carried by a set of actuator arms. Data is accessed by moving the heads from the inner to outer part of the disc (and vice-versa) driven by an actuator assembly. The heads that access sectors on discs are locked together on the actuator assembly. For this reason, all the heads move in and out together and are always physically located at the same track number (e.g., it is impossible to have one head at track 0 and another at track 500). Because all the heads move together, each of the tracks on all discs is known as a cylinder for reasons that these tracks form a cylinder since they are equal-sized circles stacked one on top of the other in space. So, for example, if a disc drive has four discs, it would normally have eight heads, and a cylinder number 680 would be made up of a set of eight tracks, one per disc surface, at track number 680. Thus, for most purposes, there is not much difference between tracks and cylinders since a cylinder is basically a set of all tracks whereat all the heads are currently located.
One of the heads must first be positioned over the correct location of a sector on the disc in order to access (i.e., read or write) the sector. This requires the heads to move to the correct track and then wait for the correct sector to pass under the appropriate head. Moving the heads to the correct track is measured by seek time. Waiting for a correct sector to pass under the appropriate head is measured by latency. Seek time and latency are two very important disc drive performance measurements. Seek time measures the amount of time required for the heads to move between tracks. Generally, the amount of time to switch between two tracks depends on the distance between the tracks; however, the relationship is not linear due to a certain amount of overhead involved in track switching. Latency, on the other hand, measures the time that the disc drive must wait for the correct sector to come around to where one of the heads is waiting for it. At the time the appropriate head arrives at and begins to follow the correct track, the actual sector for read or write may be located elsewhere on the disc spinning around at high speed. This causes a latency delay since the servo system must wait for the correct sector to arrive under the head.
A seek time delay and a latency delay are normally expressed in milliseconds. In a computing system, a millisecond is an enormous amount of time when the system memory speed is measured in nanoseconds. For example, a 200 MHz processor can theoretically execute 200,000 instructions in a millisecond. Thus, cutting the seek time and/or latency delays result in significant performance improvement in a computing system, because the computing system can execute a significant number of instructions instead of waiting for movement of the heads to a track or waiting for a correct sector to pass under one of the heads.
Particularly, storing data in a contiguous block of sectors on a track in a disc drive reduces latency. For example, latency is relatively a minor factor for reading or writing a large contiguous block of data on a track since the latency will only occur once while waiting to access the first sector of data. On the other hand, latency is an important performance-limiting factor for reading or writing noncontiguous multiple data blocks on a track.
Every sector in a disc drive is a good sector in an ideal world; however, typical disc drives contain unusable sectors when they are manufactured, because it is virtually impossible to create a disc drive with several million sectors and not have some errors. Imperfections in the media coating on the disc or other problems, for example, may make a sector inoperable. This usually shows up as an error when attempting to read the sector. Modern disc drives use an error correction code to help identify when errors occur and in some cases to correct them; however, there will still be physical flaws that prevent parts of a disc from being used. These unusable sectors, due to such physical flaws, are called defective sectors.
When defective sectors are discovered in the data storage area of a disc drive, each of the memory locations corresponding to the defective sectors are mapped to a good sector in another part of the data storage area. For this mapping purpose, spare sectors are reserved in a disc drive as substitutes for those defective sectors. Typically, each track has one spare sector at the end of the track. A disc drive controller keeps track of all defective sectors in the disc drive and automatically substitutes each of the defective sectors with a spare sector. When a host controller sends a command to read data from or write data to a defective sector, the disc drive controller seeks to the designated substitute sector taken from the pool of spare sectors rather than seeking to the defective sector. This technique is known as spare sectoring (or defect mapping) and causes defective sectors to be transparent to a user. In selecting a spare sector as a substitute, the disc drive controller always tries to use the spare sector on the same track to avoid a seek time delay associated with track switching. Nevertheless, a seek time delay cannot be avoided if more defective sectors are present on the track than available spare sectors on that track. Moreover, in most cases, mapping a defective sector to a spare sector causes fragmentation of data. Once data is fragmented, each fragment of data introduces a latency delay to locate the beginning sector of each fragment and, if the next fragment starts on a different track, an additional seek time delay is introduced. Thus, there is a big performance difference between accessing data that is laid out contiguously on a disc and that is fragmented into a dozen pieces. In any case, greater seek time and/or latency causes slower access to data stored in a disc drive.
Many types of spare sectoring techniques are known to those skilled in the art, and they include linear replacement, sector slipping, circular slipping, and segment slipping. The linear replacement technique maps each defective sector to a good spare sector located somewhere else in the disc drive. However, this technique causes the heads to jump from the defective sector to the substituted spare sector and then back to the defective sector in order to access the data in a consecutive order. A series of such required head jumps significantly degrades the system performance by adding considerable latency and seek time delays.
The sector slipping technique maintains a pool of spare sectors assigned to each track. Instead of mapping a defective sector to a spare sector located at the end of the track, this technique slips each of the defective sectors to the next closest available good sector. For example, if sector 3 is flagged as bad, the data that would have been stored there is pushed down and recorded in sector 4. The sector 4 then effectively becomes the sector 3, as each of the subsequent sectors is slipped sequentially to the next good sector on the track. The first spare sector located at the end of the track then makes up for the loss of sector 3, and so maintains the sequential order of data. This technique attempts to maintain contiguity of data within a track; however, the contiguity is broken when the number of defective sectors on the track is greater than the number of spare sectors assigned to the track. Once all spare sectors are used up, the remaining additional defective sectors cannot be slipped on the same track. In such a case, the remaining defective sectors are mapped to good sectors located on another track using, for example, the linear replacement technique as described above. Once the contiguity of data is broken, the system performance is degraded due to latency delay and seek time delay associated with accessing the fragmented data, as it is the case in the linear replacement technique.
The circular slipping technique slips all defective sectors on a track even if the number of defective sectors exceed the number of available spare sectors assigned to the track. In case the number of defective sectors exceed the number of spare sectors, some of the defective sectors are then used as a logical sector to ensure that the host controller understands that the same number of usable sectors are maintained on the track. Then the defective sector, which is used as a logical sector, is flagged as defective and is mapped to a substituting sector somewhere else in the disc drive. For example, if sectors 3 and 4 are bad on a track assigned with only one spare sector, the defective sector 3 is slipped to sector 5, and the defective sector 4 is slipped to sector 6, as the subsequent sectors are sequentially slipped. Because there is one less spare sector available, the last sector on the track wraps around the track and circularly slips to the defective sector 3, so that the constant number of usable sectors are maintained on the track. Since the sector 3 is defective, the sector 3 is then flagged as bad and is mapped to a good sector located somewhere else on the drive. As was the case in the sector slipping technique, the circular slipping technique introduces data fragmentation, and the system performance is also degraded due to the latency and seek time delays associated with accessing the noncontiguous data.
The segment slipping technique is similar to the circular slipping technique, except that the defective sectors are circularly slipped over a segment instead of over a track. A segment is a set of logically related tracks (such as a cylinder), which are positioned adjacent to each other in a disc drive. The segment is treated as one contiguous storage space such that a defective sector is slipped to a next good sector within the segment. If the number of defective sectors for the segment exceeds the number of spare sectors included in the segment, the remainder of the defective sectors are mapped to substituting sectors somewhere else in the disc drive. The concept of circular slipping can be applied to segment slipping. Once the defective sectors within the segment exceed the spare sectors per segment, the remaining logical sectors are slipped to the defective sectors starting from the first defective sector within the segment. A special case of segment slipping is cylinder slipping where the segment is a cylinder of the disc drive. Again as was the case in the sector slipping technique, the segment slipping technique introduces data fragmentation, and thus the system performance is degraded due to the latency and seek time delays associated with accessing noncontiguous data.
These prior attempts to map defective sectors to different locations in a disc drive result in data fragmentation and create system inefficiencies due to associated latency and seek time delays. What is needed is a method and system that eliminates or at least minimizes the fragmentation of data in a disc drive and thus improves the system performance by reducing latency and seek time delay in accessing data stored in a disc drive.